{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 问题：使用Python实现各种排序算法\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "面试官想从这道题中考察面试人什么？\n",
    "考排序算法的时候，可能并不一定是要你能写出来它们的实现代码，面试官可能会让你回答各个排序的基本思想，以及它们在效率上的优劣，在哪种情况下使用哪种排序是最好的。\n",
    "\n",
    "答案\n",
    "答案见拓展部分。\n",
    "\n",
    "拓展\n",
    "这个表格列出了今天我们会介绍的8种排序的时间复杂度和空间复杂度。\n",
    "\n",
    "排序法\t\t时间\t\t额外空间\n",
    "Best\tAverage\tWorst\tWorst\n",
    "冒泡排序(Bubble Sort)\tO(n)O(n)\tO(n^2)O(n \n",
    "2\n",
    " )\tO(n^2)O(n \n",
    "2\n",
    " )\tO(1)O(1)\n",
    "选择排序(Selection Sort)\tO(n^2)O(n \n",
    "2\n",
    " )\tO(n^2)O(n \n",
    "2\n",
    " )\tO(n^2)O(n \n",
    "2\n",
    " )\tO(1)O(1)\n",
    "插入排序(Insertion Sort)\tO(n)O(n)\tO(n^2)O(n \n",
    "2\n",
    " )\tO(n^2)O(n \n",
    "2\n",
    " )\tO(1)O(1)\n",
    "希尔排序(Shell Sort)\tO(nlog(n))O(nlog(n))\tO(n(log(n))^2)O(n(log(n)) \n",
    "2\n",
    " )\tO(n(log(n))^2)O(n(log(n)) \n",
    "2\n",
    " )\tO(1)O(1)\n",
    "归并排序(Merge Sort)\tO(nlog(n))O(nlog(n))\tO(nlog(n))O(nlog(n))\tO(nlog(n))O(nlog(n))\tO(n)O(n)\n",
    "快速排序(Quick Sort)\tO(nlog(n))O(nlog(n))\tO(nlog(n))O(nlog(n))\tO(n^2)O(n \n",
    "2\n",
    " )\tO(log(n))O(log(n))\n",
    "堆排序(Heap Sort)\tO(nlog(n))O(nlog(n))\tO(nlog(n))O(nlog(n))\tO(nlog(n))O(nlog(n))\tO(1)O(1)\n",
    "冒泡排序(Bubble Sort)\n",
    "基本思想：两两比较相邻记录的关键字，如果反序则交换。\n",
    "\n",
    "比如，我们给7，2，5，3，1排序\n",
    "\n",
    "7 5 2 3 1\n",
    "5 7 2 3 1 # 交换7和5\n",
    "5 2 7 3 1 # 交换7和2\n",
    "5 2 3 7 1 # 交换7和3\n",
    "5 2 3 1 7 # 交换7和1，第一轮结束，最大值7置于最后的位置\n",
    "2 5 3 1 7 # 重头开始\n",
    "… # 重复上述步骤，直到倒数第二大的值位于倒数第二的位置，如此反复\n",
    "def bubble_sort(nums):\n",
    "    for i in range(len(nums) - 1): # 遍历 len(nums)-1 次\n",
    "        for j in range(len(nums) - i - 1): # 已排好序的部分不用再次遍历\n",
    "            if nums[j] > nums[j+1]:\n",
    "                nums[j], nums[j+1] = nums[j+1], nums[j] # 交换两个数不用中间变量\n",
    "    return nums\n",
    "冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。我们发现它最坏的情况下要执行\n",
    "n + (n-1) + (n-2) + ... + 2 + 1n+(n−1)+(n−2)+...+2+1 次交换，所以它的时间复杂度为 O(n^2)O(n \n",
    "2\n",
    " )。\n",
    "\n",
    "选择排序(Selection Sort)\n",
    "基本思想：选择排序不受输入数据的影响，即在任何情况下时间复杂度不变。选择排序每次选出最小的元素，因此需要遍历 n-1 次。\n",
    "\n",
    "7 5 2 3 1 => 最小数索引为0\n",
    "比较7和5 => 最小数索引为1\n",
    "比较5和2 => 最小数索引为2\n",
    "比较2和3 => 最小数索引为2\n",
    "比较2和1 => 最小数索引为4\n",
    "将1和7互换，结束第一轮，第二轮从索引1的位置开始，找出第二小的数并放置在索引1的位置\n",
    "所以，选择排序任何情况下要执行 n + (n-1) + (n-2) + ... + 2 + 1n+(n−1)+(n−2)+...+2+1 次更新最小值索引，即它的时间复杂度为 O(n^2)O(n \n",
    "2\n",
    " )。。\n",
    "\n",
    "def selection_sort(nums):\n",
    "    for i in range(len(nums) - 1):  # 遍历 len(nums)-1 次\n",
    "        minIndex = i\n",
    "        for j in range(i + 1, len(nums)):\n",
    "            if nums[j] < nums[minIndex]:  # 更新最小值索引\n",
    "                minIndex = j  \n",
    "        nums[i], nums[minIndex] = nums[minIndex], nums[i] # 把最小数交换到前面\n",
    "    return nums\n",
    "选择排序处于和冒泡排序都只是排序算法发展的初级阶段，在实际中使用较少。\n",
    "\n",
    "插入排序(Insertion Sort)\n",
    "基本思想：将一个记录插入到已经排好序的有序表中，从而得到一个新的，录数增1的有序表。你可以把这种排序想象成整理扑克牌，当你拿到一个新牌要插入已排好序的一把牌中。\n",
    "\n",
    "Tips: 插入排序适用于数量较小，部分或者全部排序过的列表。\n",
    "\n",
    "def insertion_sort(nums):\n",
    "    for i in range(len(nums)): # 遍历 len(nums) 次\n",
    "         # cursor 保存当前待插入的数\n",
    "        cursor = nums[i]\n",
    "        pos = i\n",
    "\n",
    "        while pos > 0 and nums[pos - 1] > cursor:\n",
    "            # 将比 cursor 大的元素向后移动\n",
    "            nums[pos] = nums[pos - 1]\n",
    "            pos = pos - 1\n",
    "\n",
    "        nums[pos] = cursor  # 待插入的数的正确位置\n",
    "    return nums\n",
    "希尔排序（Shell Sort)\n",
    "基本思想：分组插入排序，即通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。\n",
    "\n",
    "Tips: 如何分组以及每组步长的选择直接决定了希尔排序的复杂度。所以，它是不稳定的。\n",
    "\n",
    "index\t0\t1\t2\t3\t4\t5\n",
    "num\t1\t9\t3\t2\t5\t8\n",
    "gap=3\t^\t\t\t^\t\t\n",
    "def shell_sort(nums):\n",
    "    gap = len(nums) // 2\n",
    "    while gap > 0:\n",
    "        for i in range(gap, len(nums)):\n",
    "            cursor = nums[i]\n",
    "            pos = i\n",
    "            while pos >0 and nums[pos - gap] > cursor: # 比较gap的两头，如果左边的比右边的大就互换位置。比如：第一轮，比较index=0和index=3的两个数，\n",
    "                nums[pos] = nums[pos - gap]\n",
    "                pos = pos - gap\n",
    "            nums[pos] = cursor\n",
    "        gap = gap // 2 # gap取半，直到gap=0，整个循环结束，当gap=1的时候，即最后一轮就和上面的插入排序一样了。\n",
    "\n",
    "    return nums\n",
    "归并排序（Merge Sort）\n",
    "基本思想：它的中心思想就是先递归分解数组，再合并数组，这是分治法的一个非常典型的应用。先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。\n",
    "\n",
    "Tips: 分治法是一种算法设计策略。它的思想是将原始问题划分为n个规模较小且与原问题相似的子问题，然后递归的解决子问题，再合并结果，即得到原问题的解。大体上，每一层递归都包含三个步骤：分解，解决，合并。\n",
    "分解： 将n个元素分成n/2个元素的子序列；\n",
    "解决： 用合并排序法对两个子序列递归地排序；\n",
    "合并： 合并两个已排序的子序列已得到排序结果。\n",
    "\n",
    "def merge_sort(nums):\n",
    "    # 归并过程\n",
    "    def merge(left, right):\n",
    "        # left， right是已排好序的两个子序列\n",
    "        result = []  # 保存归并后的结果\n",
    "        i = j = 0 # i:左序列的游标， j:右序列的游标\n",
    "        while i < len(left) and j < len(right):\n",
    "            # 比较左右序列游标所指的值，较小的那个被取出放入result中，且该序列游标右移\n",
    "            if left[i] <= right[j]:\n",
    "                result.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                result.append(right[j])\n",
    "                j += 1\n",
    "        result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾\n",
    "        return result\n",
    "\n",
    "    # 递归过程\n",
    "    if len(nums) <= 1:\n",
    "        return nums\n",
    "    mid = len(nums) // 2\n",
    "    left = merge_sort(nums[:mid])\n",
    "    right = merge_sort(nums[mid:])\n",
    "    return merge(left, right)\n",
    "快速排序（Quick Sort）\n",
    "基本思想：它也是分治法的一个典型应用。\n",
    "\n",
    "步骤：\n",
    "\n",
    "从数列中挑出一个元素作为基准数。\n",
    "分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。\n",
    "再对左右区间递归执行第二步，直至各区间只有一个数。\n",
    "def quick_sort(nums):\n",
    "    # 选取最后一个元素作为基准数\n",
    "    return qsort(nums, 0, len(nums)-1)\n",
    "\n",
    "def qsort(nums, left, right):\n",
    "    #快排函数，nums为待排序数组，left为待排序的左边界，right为右边界\n",
    "    if left >= right :\n",
    "        return nums\n",
    "    key = nums[left]    #取最左边的为基准数\n",
    "    lp = left           #左指针\n",
    "    rp = right          #右指针\n",
    "    while lp < rp :\n",
    "        # 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边\n",
    "        while nums[rp] >= key and lp < rp : # rp所指的数值大于基数，即右边的数保持不动，指针继续左移直到所指的数小于基数或者和左指针重合\n",
    "            rp -= 1\n",
    "        while nums[lp] <= key and lp < rp : # lp所指的数值大于基数，即左边的数保持不动，指针右移直到所指的数大于基数或者和右指针重合\n",
    "            lp += 1\n",
    "\n",
    "        # 左指针和右指针所指的数值交换，这样满足比基准数大的放到右边，小于或等于它的数都放到左边\n",
    "        nums[lp], nums[rp] = nums[rp], nums[lp]\n",
    "\n",
    "    # 将基数和lp所指的数交换位置\n",
    "    nums[left], nums[lp] = nums[lp], nums[left]\n",
    "\n",
    "    # 递归过程，分解更小的组\n",
    "    qsort(nums, left, lp-1)\n",
    "    qsort(nums, rp+1, right)\n",
    "\n",
    "    return nums\n",
    "堆排序（Heap Sort）\n",
    "基本思想：采用堆的数据结构进行排序。在堆排序中，用到的是最大堆，即父节点的数要大于其子节点的数值，每个节点的值至多和其父节点的值一样大，堆中的最大元素存放在根节点中。\n",
    "\n",
    "下面列出了堆排序中的一些基本过程：\n",
    "\n",
    "构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是最大堆，则从下标n/2开始的元素均为最大堆。于是只要从n/2-1开始，向前依次构造最大堆，这样就能保证，构造到某个节点时，它的左右子树都已经是最大堆。\n",
    "堆排序（HeapSort）：得到一个最大堆后，每次从根部移除一个节点，但是剩余的元素仍然要保持最大堆的特性。\n",
    "最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点。若某个节点的位置为i，那么它的左节点位置为2i，右节点的位置为2i+1。\n",
    "index\t1\t2\t3\t4\t5\t6\t7\t8\t9\t10\n",
    "nums\t16\t14\t10\t8\t7\t9\t3\t2\t4\t1\n",
    "上面这组数就是一个最大堆，对于位置1的子节点，左节点位置为2 * 12∗1，右节点的位置为2 * 1 + 12∗1+1。\n",
    "\n",
    "16\n",
    "14\n",
    "10\n",
    "8\n",
    "7\n",
    "9\n",
    "3\n",
    "2\n",
    "4\n",
    "1\n",
    "def heap_sort(nums) :\n",
    "    n = len(nums)\n",
    "    first = int(n/2-1)       #最后一个非叶子节点\n",
    "    for start in range(first,-1,-1):     #构造最大堆，自下而上\n",
    "        max_heapify(nums,start,n-1)\n",
    "    for end in range(n-1,0,-1):           #堆排，将最大堆转换成有序数组\n",
    "        nums[end],nums[0] = nums[0],nums[end]\n",
    "        max_heapify(nums,0,end-1)\n",
    "    return nums\n",
    "\n",
    "#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点\n",
    "#start为当前需要调整最大堆的位置，end为调整边界\n",
    "def max_heapify(ary, start, end):\n",
    "    root = start\n",
    "    while True :\n",
    "        child = root*2 +1               #调整节点的子节点\n",
    "        if child > end : break\n",
    "        if child+1 <= end and ary[child] < ary[child+1] :\n",
    "            child = child+1             #取较大的子节点\n",
    "        if ary[root] < ary[child] :     #较大的子节点成为父节点\n",
    "            ary[root],ary[child] = ary[child],ary[root]     #交换\n",
    "            root = child\n",
    "        else :\n",
    "            break\n",
    "趣味问题：字符串 “123” 转换成 123，不使用内置函数 int？\n",
    "面试官想从这道题中考察面试人什么？\n",
    "这个问题关键在于不能用内置函数int，从算法的层面来说，其难易程度算比较简单的。它考的是面试者的解决问题的能力。\n",
    "\n",
    "答案\n",
    "def str2int(s):\n",
    "    s = s[::-1]\n",
    "    num = 0\n",
    "    for i, v in enumerate(s):\n",
    "        for j in range(0, 10):\n",
    "            if v == str(j): # 用两个string进行比较，这样就避开了int\n",
    "                num += j * (10 ** i)\n",
    "   return num\n",
    "拓展\n",
    "这道题，其实还有很多其它解法，如果不用内置函数int，还有其它很多内置函数同样可以实现字符转数字的功能。我们还可以利用ord求出每一位字符的ASCII码再减去字符0的ASCII码求出每位表示的数字大写。\n",
    "\n",
    "def str2int(s):\n",
    "    s = s[::-1]\n",
    "    num = 0\n",
    "    for i, v in enumerate(s):\n",
    "        offset = ord(v) - ord('0')\n",
    "        num += offset * (10 ** i)\n",
    "    return num\n",
    "小结\n",
    "本节主要解析了几道经典的算法题以及做算法题要注意的事项，引入了Big O notation概念和分治法。\n",
    "\n",
    "数学知识在解算法题的时候会经常充当着非常重要的角色，就像本节中的第一个问题，斐波那契数列，最后一个算法设计完全依赖于数学知识，而且性能上也大大提升。\n",
    "\n",
    "另外，排序在算法中必不可少，几乎每个算法书都会讲到。性能高的排序可以在重量级数据的工程项目中发挥重要作用。简单直接的排序算法通常以O(n^2)O(n \n",
    "2\n",
    " )时间运行。有很多种排序算法，比如归并排序（Mergesort），堆排序（Heapsort）和快速排序（Quicksort）的时间复杂度是O(n*logn)O(n∗logn)。 每种方法都有其优点和缺点：例如，堆排序是原地排序（in-place）算法，即输入的数据通常会被要输出的部份覆盖掉，这样不会有额外的空间，但是不稳定。归并排序是稳定的，但不是原地算法。\n",
    "\n",
    "在本节的最后是一道比较简单的编程题，有点像脑筋急转弯，在面试的时候，多留意题目中给出的信息。\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}